Optimization Problems
The object of an optimization problem is finding the best solution amongst a set of possible solutions. Optimization problems are in contrast to decision problems, where the object is to arrive at a yes or no answer.
Constraint Satisfaction Problems
Constraint satisfaction problems (CSPs) are problems defined as a set of objects whose state must satisfy a number of constraints. The constraints are expressed over variables. A solver for a CSP solves the CSP by finding the configuration of variables that satisfies the constraints. Constraint satisfaction problems may be solved using combinatorial searches, heuristics, combinations of these, and the like.
Quadratic Unconstrained Binary Optimization Problems
A quadratic unconstrained binary optimization (QUBO) problem is a form of discrete optimization problem that involves finding a set of N binary variables {xi} that minimizes an objective function of the form:
      E    ⁡          (                        x          1                ,        …        ⁢                                  ,                  x          N                    )        =            ∑              i        ≤        j            N        ⁢                  Q        ij            ⁢              x        i            ⁢              y        j            where Q is typically a real-valued upper triangular matrix that is characteristic of the particular problem instance being studied. QUBO problems and applications arise in many different fields, for example machine learning, pattern matching, and statistical mechanics, to name a few.Linear Programming
Linear programming is a method for finding a solution to a combined problem of optimization and solving systems of linear equations. Linear programming is a method for the optimization of a linear objective function subject to linear constraints expressed as equalities and inequalities. The optimal value can be a minimum or a maximum. This can have the form:Optimize cx, subject to Ax=b and subject to x≥0where c and b are vectors of coefficients, A is a matrix defining the linear system of equalities, and x is the vector of variables to be determined. The product cx is the objective function to be minimized or maximized. The form of the statement above can be expressed as a series of equalities and inequalities. Linear programming can be used with many problem types including: planning, routing, scheduling, assignment, and portfolio optimization.Satisfiability Problems
Satisfiability problems (SAT) are a set of decision problems for determining if there a set of values that satisfy a Boolean formula. SAT can determine whether the set of values for a set of variables, called a truth assignment, causes the Boolean formula to evaluate to true. The Boolean formula is made from a series of literals: a Boolean variable or its negation. These literals are then joined into clauses and then joined into the Boolean formula using operators. The form of the clauses and the operator which are used define the subclass of the problems. For example, if there are three literals in the clauses, then the problem is in 3SAT. If the literals are joined by OR operators and the clauses by AND operators the problem is CNF-3SAT. SAT was the first known NP-complete problem. Satisfiability problems arise in industrial applications, computational problems, and the like.
Quantum Annealing
Quantum annealing is a heuristic optimization approach applicable to certain discrete optimization problems. For example, quantum annealing can be used to find a low-energy state of a system, such as the ground state of the system.
Similar in concept to classical annealing, the method relies on the underlying principle that natural systems tend toward lower energy states because lower energy states are more stable. Whereas classical annealing can use classical thermal fluctuations to guide a system to its global energy minimum, quantum annealing can use natural quantum fluctuations, such as quantum tunneling, to reach a global energy minimum more accurately and/or more quickly.
Since the solution to a hard problem, such as a combinatorial optimization problem, can be encoded in the ground state of a system, quantum annealing can be used to find the solution to such hard problems.
Equivalence of QUBO to Ising Model
Quantum hardware can be used to minimize the dimensionless energy of an Ising model mathematically equivalent to the QUBO described above:
      E    ⁡          (                        s          |          h                ,        J            )        =                    ∑                  i          ∈                      V            ⁡                          (              G              )                                                                    ⁢                        h          i                ⁢                  s          i                      +                  ∑                              (                          i              ,              j                        )                    ∈                      E            ⁡                          (              G              )                                                                    ⁢                        J                      i            ,            j                          ⁢                  s          i                ⁢                  s          j                    where spin variables si∈{−1,1} are indexed by the vertices V(G) of a graph G corresponding to a hardware device allowing pairwise interactions given by the edges E(G) of the graph G. The coefficients (also known as the programmable parameters) hi and Ji,j are dimensionless and real-valued.
A quantum annealing process can minimize the Ising energy by evolving the ground state of an initial Hamiltonian to the ground state of a problem Hamiltonian. The ground state of the initial Hamiltonian is a superposition state in which all spin configurations are equally likely. After annealing, the spin configurations with the smallest energy with respect to the problem Hamiltonian are the most likely to be measured.
The efficiency of quantum annealing depends at least in part on the energy gap separating ground and excited states during evolution. Different representations of an optimization problem can have different quantum gaps.
Practical Implementation of Quantum Annealing
The techniques described in the present application relate to problem representations ameliorating limitations imposed by current hardware.
Physical devices can impose limitations on the precision to which the system can specify the programmable coefficients h,J of the Ising model described above. Moreover, the Ising model is only an approximation to the underlying physics, and there can be systematic errors causing a discrepancy between the programmable coefficients and the effective Ising approximation. Consequently, it can be desirable to seek problem representations that are less sensitive to control errors.
Technological limitations can restrict the range of energy scales of programmable coefficients h,J relative to the thermal energy kBT. For problems having few ground states and exponentially many excited states within kBT, where kB is the Boltzmann constant and T is the temperature. A limited range of energy scales of programmable coefficients h,J can make quantum annealing challenging.
It can be difficult to realize all pairwise couplings in a hardware device, since the number of potential couplings grows as the square of the number of qubits in the system. As a result, quantum annealing hardware capable of accommodating a large number of variables can offer only sparse connectivity. Discrete optimization problems of practical interest can require greater connectivity.
Quantum annealing through minimizing the Ising energy can be challenging for a large number of variables, and real-world problems typically can need a very large number of variables. Moreover, translating a discrete optimization problem into a sparse Ising model can require the addition of ancillary (or helper) variables, thereby increasing the size of the problem even further.